package simple;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Queue;

/**
 * 3. 无重复字符的最长子串
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * */

public class LongestOfSubstring {
    /**
     * 暴力求解:时间复杂度O(n^2) 空间复杂度 O(m) m为最大无重复字符的子串长度
     * */
    public int lengthOfSubstring(String s){
        HashSet hs = new HashSet();
        int tempLength = 0;
        for (int i = 0; i < s.length(); i++) {
            hs.clear();
            for (int j = i; j < s.length(); j++){
                // 如果包含重复字符，就将长度记录下来，开始新的子串的构造
                if (hs.contains(s.charAt(j))){
                    tempLength = Math.max(tempLength, hs.size());
                    break;
                }else{// 如果没有包含重复字符，将长度记录下来
                    hs.add(s.charAt(j));
                    tempLength = Math.max(tempLength, hs.size());
                }
            }
        }
        return tempLength;
    }

    // 窗口滑动（指针移动法） 时间复杂度：O(n) 空间复杂度：O(m)
    public int lengthOfSubstring1(String s){
        HashMap<Character,Integer> hm = new HashMap<>();
        int max = 0;
        for (int i = 0, j = 0; j < s.length(); j++){
            // 如果哈希map中包含这个字符，我们就把指针i移动到这个字符的位置后一个（HashMap中的字符）
            if (hm.containsKey(s.charAt(j))){
                // 这里用max因为后面出现的重复字符在HashMap的位置可能在i的前面
                i = Math.max(i, hm.get(s.charAt(j)) + 1);
            }
            hm.put(s.charAt(j), j);
            // 长度为末尾位置减去起始位置加1
            max = Math.max(max, j-i+1);
        }
        return max;
    }

    // 利用队列求解 时间复杂度：O(xn) x为重复元素个数 空间复杂度：O(m)
    public int lengthOfSubstring2(String s){
        int max = 0;
        Queue<Character> queue = new ArrayDeque<>();
        for (char c : s.toCharArray()){
            while(queue.contains(c)){
                // 如果有重复的元素就一直出队
                queue.poll();
            }
            // 添加到队尾
            queue.add(c);
            max = Math.max(max, queue.size());
        }
        return max;
    }


    // main
    public static void main(String[] args) {
        LongestOfSubstring m = new LongestOfSubstring();
        System.out.println(m.lengthOfSubstring2("abba"));
    }
}
